//算法代码在这
//主函数部分：第285行
//三个函数都以如下描述：
//用矩形(left, top),(left, bottom),(right, bottom),(right, top)裁剪直线(x1, y1),(x2, y2), 
//返回一个{新的x1,y1,x2,y2}被裁剪的直线，
//若裁剪之后的直线不存在，返回null


//Cohen-Sutherland算法

//Cohen-Sutherland算法辅助函数
function encode(left, right, top, bottom, x, y) {
  let res = '';
  if (x < left) {
    res = '1';
  } else {
    res = '0';
  }
  if (x > right) {
    res = '1' + res;
  } else {
    res = '0' + res;
  }
  if (y < bottom) {
    res = '1' + res;
  } else {
    res = '0' + res;
  }
  if (y > top) {
    res = '1' + res;
  } else {
    res = '0' + res;
  }
  return parseInt(res, 2);
}


//Cohen-Sutherland算法主函数
function cohen(left, right, top, bottom, x1, y1, x2, y2) {
  let code1 = encode(left, right, top, bottom, x1, y1);
  let code2 = encode(left, right, top, bottom, x2, y2);
  if ((code1 | code2) === 0) { //简而取之
    log('简而取之');
    return {
      x1,
      y1,
      x2,
      y2
    };
  }
  if ((code1 & code2) !== 0) { //简而去之
    log('简而去之');
    return null;
  }
  if (code1 === 0) { //确保p1在窗口外
    log('发生交换');
    let temp = code2;
    code2 = code1;
    code1 = temp;
    temp = x1;
    x1 = x2;
    x2 = temp;
    temp = y1;
    y1 = y2;
    y2 = temp;
  }
  let k = (y2 - y1) / (x2 - x1);
  //左
  let l = Math.floor(y1 + k * (left - x1));
  log('左边界交点：', left, l);
  if (encode(left, l) === 0) {
    log('左边界切割');
    return cohen(left, right, top, bottom, left, l, x2, y2);
  }
  //右
  let r = Math.floor(y1 + k * (right - x1));
  log('右边界交点：', right, r);
  if (encode(right, r) === 0) {
    log('右边界切割');
    return cohen(left, right, top, bottom, right, r, x2, y2);
  }
  //上
  let t = Math.floor(x1 + (top - y1) / k);
  log('上边界交点：', t, top);
  if (encode(t, top) === 0) {
    log('上边界切割');
    return cohen(left, right, top, bottom, t, top, x2, y2);
  }
  //下
  let b = Math.floor(x1 + (bottom - y1) / k);
  log('下边界交点：', b, bottom);
  if (encode(b, bottom) === 0) {
    log('下边界切割');
    return cohen(left, right, top, bottom, b, bottom, x2, y2);
  }
}

//中点分割算法

//中点分割算法辅助函数
function midHelper(left, right, top, bottom, x1, y1, x2, y2, restrict) { //距离p0最远可见点
  let code2 = encode(left, right, top, bottom, x2, y2);
  if (code2 === 0) {
    return {
      x2,
      y2
    };
  }
  if (((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)) <= (restrict * restrict)) {
    return {
      x2,
      y2
    };
  }
  let mx = (x1 + x2) >> 1;
  let my = (y1 + y2) >> 1;
  let isPmInWindow = (mx <= right) && (mx >= left) && (my <= top) && (my >= bottom);
  let isP1InWindow = (x1 <= right) && (x1 >= left) && (y1 <= top) && (y1 >= bottom);
  if (isPmInWindow) { //中点在窗口内
    log('中点在窗口内');
    return midHelper(left, right, top, bottom, x2, y2, mx, my, restrict);
  }
  if (!isP1InWindow && !isPmInWindow) { //中点和p1都在窗口外侧
    log('中点和p1都在窗口外侧');
    return midHelper(left, right, top, bottom, x1, y1, mx, my, restrict);
  }
  if ((isP1InWindow && !isPmInWindow) || (!isP1InWindow && isPmInWindow)) { //中点和p1在窗口异侧
    log('中点和p1在窗口异侧');
    return midHelper(left, right, top, bottom, x2, y2, mx, my, restrict);
  }
}

//中点分割算法主函数
function midDivision(left, right, top, bottom, x1, y1, x2, y2, restrict) {
  let code1 = encode(left, right, top, bottom, x1, y1);
  let code2 = encode(left, right, top, bottom, x2, y2);
  if ((code1 | code2) === 0) { //简而取之
    log('简而取之');
    return {
      x1,
      y1,
      x2,
      y2
    };
  }
  if ((code1 & code2) !== 0) { //简而去之
    log('简而去之');
    return null;
  }
  let temp = midHelper(left, right, top, bottom, x1, y1, x2, y2, restrict);
  return {
    x1: temp.x2, //距离p0的最远可见点
    y1: temp.y2,
    ...midHelper(left, right, top, bottom, x2, y2, x1, y1, restrict) //距离p1的最远可见点
  }
}

// Liang-Barsky算法

function liang(x1, y1, x2, y2, wxl, wxr, wyt, wyb) {
  let p1 = -(x2 - x1);
  let p2 = x2 - x1;
  let p3 = -(y2 - y1);
  let p4 = y2 - y1;
  let q1 = x1 - wxl;
  let q2 = wxr - x1;
  let q3 = y1 - wyb;
  let q4 = wyt - y1;
  if (x1 - x2 === 0) {
    log('Δx = 0');
    if (q1 < 0 || q2 < 0) {
      log('q1 < 0 || q2 < 0, 删去');
      return false;
    } else {
      log('q1 >= 0 && q2 >= 0');
      umax,
      umin,
      us,
      ub;
      if (p3 > 0) {
        ub = q3 / p3;
        us = q4 / p4;
      } else {
        us = q3 / p3;
        ub = q4 / p4;
      }
      if (us > 0) {
        umax = us;
      } else {
        umax = 0;
      }
      if (ub < 1) {
        umin = ub;
      } else {
        umin = 1;
      }
      if (umax > umin) {
        return false;
      } else {
        umax = umax;
        umin = umin;
        return true;
      }
    }
  } else if (y2 - y1 === 0) {
    log('Δy == 0');
    if (q3 < 0 || q4 < 0) {
      log('q3 < 0 || q4 < 0, 删去');
      return false;
    } else {
      umax,
      umin,
      us,
      ub;
      if (p1 > 0) {
        ub = q1 / p1;
        us = q2 / p2;
      } else {
        us = q1 / p1;
        ub = q2 / p2;
      }
      if (us > 0) {
        umax = us;
      } else {
        umax = 0;
      }
      if (ub < 1) {
        umin = ub;
      } else {
        umin = 1;
      }
      if (umax > umin) {
        return false;
      } else {
        umax = umax;
        umin = umin;
        return true;
      }
    }
  } else {
    log('Δx != 0 && Δy != 0');
    let umax, umin, ub1, ub2, us1, us2;
    if (p1 > 0) {
      ub1 = q1 / p1;
      us1 = q2 / p2;
    } else {
      us1 = q1 / p1;
      ub1 = q2 / p2;
    }
    if (p3 > 0) {
      ub2 = q3 / p3;
      us2 = q4 / p4;
    } else {
      us2 = q3 / p3;
      ub2 = q4 / p4;
    }
    if (0 >= us1 && 0 >= us2) {
      umax = 0;
    } else if (us1 >= 0 && us1 >= us2) {
      umax = us1;
    } else {
      umax = us2;
    }
    if (1 <= ub1 && 1 <= ub2) {
      umin = 1;
    } else if (ub1 <= 1 && ub1 <= ub2) {
      umin = ub1;
    } else {
      umin = ub2;
    }
    if (umax > umin) {
      return false;
    } else {
      return {
        x1: Math.floor(x1 + umax * (x2 - x1) + 0.5),
        y1: Math.floor(y1 + umax * (y2 - y1) + 0.5),
        x2: Math.floor(x1 + umin * (x2 - x1) + 0.5),
        y2: Math.floor(y1 + umin * (y2 - y1) + 0.5)
      }
    }
  }
}


//main

function printWithCohen() {
  log('----Cohen-Sutherland算法----');
  ctx.fillStyle = "#ccc";
  dda(x1, y1, x2, y2);
  ctx.fillStyle = RED;
  let temp = cohen(l, r, t, b, x1, y1, x2, y2);
  if (temp) {
    dda(temp.x1, temp.y1, temp.x2, temp.y2);
    log('最终切割结果:(' + temp.x1 + ', ' + temp.y1 + '), (' + temp.x2 + ', ' + temp.y2 + ')');
  } else {
    log('直线显然不可见')
  }
}

function printWithMid() {
  log('--------中点分割算法---------');
  ctx.fillStyle = "#ccc";
  dda(x1, y1, x2, y2);
  ctx.fillStyle = GREEN;
  temp = midDivision(l, r, t, b, x1, y1, x2, y2, 1);
  if (temp) {
    dda(temp.x1, temp.y1, temp.x2, temp.y2);
    log('最终切割结果:(' + temp.x1 + ', ' + temp.y1 + '), (' + temp.x2 + ', ' + temp.y2 + ')');
  } else {
    log('直线显然不可见')
  }
}

function printWithLiang() {
  log('------Liang-Barsky算法------');
  ctx.fillStyle = "#ccc";
  dda(x1, y1, x2, y2);
  ctx.fillStyle = BLUE;
  temp = liang(x1, y1, x2, y2, l, r, t, b);
  if (temp) {
    dda(temp.x1, temp.y1, temp.x2, temp.y2);
    log('最终切割结果:(' + temp.x1 + ', ' + temp.y1 + '), (' + temp.x2 + ', ' + temp.y2 + ')');
  } else {
    log('直线显然不可见')
  }
}